﻿using System;
using System.Diagnostics.Contracts;
using System.Threading;

namespace O1.Storage
{
    [ContractVerification(true)]
    public class BlockArray<T>
    {
        internal const int BlockSize = 524288;

        internal const int BlockSizeLog2 = 19;

        private T[][] storage;

        private long length;

        public BlockArray(long initialCapacity)
        {
            Contract.Requires<ArgumentOutOfRangeException>(initialCapacity > -1);

            Contract.Ensures(this.storage != null);

            this.length = initialCapacity;
            int blocks = unchecked((int)(initialCapacity / BlockSize));
            if (blocks * BlockSize <= initialCapacity)
            {
                blocks += 1;
            }

            var s = new T[blocks][];
            for (int i = 0; i < s.Length - 1; i++)
            {
                s[i] = new T[BlockSize];
            }

            Contract.Assert(blocks == s.Length);
            s[blocks - 1] = new T[initialCapacity % BlockSize];
            this.storage = s;
        }

        public long Length
        {
            get
            {
                return this.length;
            }
        }

        [ContractVerification(false)]
        public T this[long index]
        {
            get
            {
                return this.storage[(int)(index >> BlockSizeLog2)][(int)(index & (BlockSize - 1))];
            }

            set
            {
                this.storage[(int)(index >> BlockSizeLog2)][(int)(index & (BlockSize - 1))] = value;
            }
        }

        public void Expand(long newSize)
        {
            Contract.Requires(newSize > 0);
            Contract.Ensures(this.length >= newSize);

            lock (this.storage)
            {
                this.SynchronizedExpand(newSize);
            }
        }

        private void SynchronizedExpand(long newSize)
        {
            Contract.Requires(newSize > 0);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.length >= newSize);

            var size = this.length;
            Contract.Assert(size == this.length);

            if (newSize <= size)
            {
                Contract.Assert(this.length >= newSize);
                return;
            }

            Contract.Assert(newSize > this.length);

            int newBlockCount = (int)(newSize / BlockSize);
            if (newBlockCount * BlockSize < newSize)
            {
                newBlockCount += 1;
            }

            Contract.Assert(newBlockCount > (int)(size / BlockSize));
            Contract.Assume(newBlockCount > this.storage.Length);

            var expanded = new T[newBlockCount][];
            Array.Copy(this.storage, expanded, this.storage.Length);

            for (var i = this.storage.Length; i < newBlockCount; i++)
            {
                expanded[i] = new T[BlockSize];
            }

            this.length = newSize;
            this.storage = expanded;

            Contract.Assert(this.length >= newSize);
        }

        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(this.storage != null);
        }
    }
}